#include <iostream>
template<typename T>
void insertionSort(T arr[], int n){
	for(int i = 1; i < n; ++i){		// 第0个元素本身有序
		/**
		 *	寻找arr[i] 元素合适的插入位置
		 *  从前向后找,只找到第一个元素和初始0比较   0 < j <= i
		 *  如果比前面元素小则交换位置
		 *  循环条件放入 for中，类似 break效果
		 */ 
		for(int j = i; j > 0 && arr[j] < arr[j - 1]; --j){	
			swap(arr[j], arr[j - 1]);
		}
	}
}
